
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * 第一遍
     * @param nums
     * @param target
     * @return
     */
//    public int threeSumClosest(int[] nums, int target) {
//        if (nums.length < 3) return 0;
//        Arrays.sort(nums);
//        int delta = Integer.MAX_VALUE;
//        for (int i = 0; i < nums.length - 2; i++) {
//            int threeSum = nums[i] + twoSumClosest(nums, i + 1, target - nums[i]);
//            if (Math.abs(delta) > Math.abs(target - threeSum)) {
//                delta = target - threeSum;
//            }
//        }
//        return target - delta;
//    }
//
//    // 搜索最接近target的两数之和
//    int twoSumClosest(int[] nums, int start, int target) {
//        int L = start, R = nums.length - 1;
//        // 记录两数之和与目标值的偏差
//        int delta = Integer.MAX_VALUE;
//        while (L < R) {
//            int sum = nums[L] + nums[R];
//            if (Math.abs(delta) > Math.abs(target - sum)) {
//                // 偏差大于target-sum
//                delta = target - sum;
//            }
//            if (sum < target) {
//                L++;
//            } else {
//                R--;
//            }
//        }
//        return target - delta;
//    }


    /**
     * 第二遍
     * @param nums
     * @param target
     * @return
     */
//    public int threeSumClosest(int[] nums, int target) {
//        if (nums.length < 3) return 0;
//        Arrays.sort(nums);
//        // delta记录三数之和与目标的偏差值
//        int delta = Integer.MAX_VALUE;
//        for (int i = 0; i < nums.length - 2; i++) {
//            int threeSum = nums[i] + twoSumClosest(nums, i + 1, target - nums[i]);
//            if (Math.abs(delta) > Math.abs(target - threeSum)) {
//                delta = target - threeSum;
//            }
//        }
//        // 返回的就是最优的sum[L] + sum[R] + sum[i]
//        return target - delta;
//    }
//
//    // 搜索最接近target的两数之和
//    int twoSumClosest(int[] nums, int start, int target) {
//        int L = start, R = nums.length - 1;
//        // delta记录两数之和与目标的偏差值
//        int delta = Integer.MAX_VALUE;
//        while (L < R) {
//            int sum = nums[L] + nums[R];
//            // 如果偏差值大于目标的偏差值，则修改delta为新的偏差值，因为题目要最接近嘛
//            if (Math.abs(delta) > Math.abs(target - sum)) {
//                delta = target - sum;
//            }
//            if (target > sum) {
//                L++;
//            } else {
//                R--;
//            }
//        }
//        // 返回的就是最优的sum[L] + sum[R]
//        return target - delta;
//    }


    /**
     * 第三遍 2/24
     * @param nums
     * @param target
     * @return
     */
//    public int threeSumClosest(int[] nums, int target) {
//        if (nums.length < 3) return 0;
//
//        // 首先进行排序
//        Arrays.sort(nums);
//        // 偏差值记录: 三数之和与目标值的偏差记录
//        int detal = Integer.MAX_VALUE;
//        for (int i = 0; i < nums.length - 2; i++) {
//            int sum = nums[i] + twoSumClosest(nums, i+1, target - nums[i]);
//            if (Math.abs(detal) > Math.abs(target - sum)) {
//                detal = target - sum;
//            }
//        }
//        return target - detal;
//    }
//
//    // 在 nums[start..] 搜索最接近 target 的两数之和
//    int twoSumClosest(int[] nums, int start, int target) {
//        int lo = start, hi = nums.length - 1;
//        int detal = Integer.MAX_VALUE;
//        while (lo < hi) {
//            int sum = nums[lo] + nums[hi];
//            if (Math.abs(detal) > Math.abs(target - sum)) {
//                detal = target - sum;
//            }
//            if (sum < target) {
//                lo++;
//            } else {
//                hi--;
//            }
//        }
//        return target - detal;
//    }


    /**
     * 第四遍 2/27
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) return 0;

        // 首先排序
        Arrays.sort(nums);
        // 记录偏差值
        int delta = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int sum = nums[i] + twoSumClosest(nums, i + 1, target - nums[i]);
            if (Math.abs(delta) > Math.abs(target - sum)) {
                delta = target - sum;
            }
        }
        return target - delta;
    }

    int twoSumClosest(int[] nums, int start, int target) {
        int lo = start, hi = nums.length - 1;
        // 记录偏差值
        int delta = Integer.MAX_VALUE;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            if (Math.abs(delta) > Math.abs(target - sum)) {
                delta = target - sum;
            }
            if (sum > target) {
                hi--;
            } else {
                lo++;
            }
        }
        return target - delta;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
